package debtbundler.domain.bll.solver;

import java.util.Collection;
import java.util.logging.Level;
import java.util.logging.Logger;

import debtbundler.domain.entity.Person;
import debtbundler.mathematics.GaussianLinSysSolver;

/**
 * A solver that checks if the solution to the debt problem is unique and solves that
 * quickly. If not, tries to minimize number of debts by matching debtors 
 * and creditors in random orders. 
 * 
 * @author Anssi
 *
 */
public class HybridSolver extends RandomizedSolver {
	private static Logger logger = Logger.getLogger(HybridSolver.class.getName());
	
	/** Coefficient matrix of linear equation system of debts */ 
	private double[][] A; 
	/** Right-hand side vector of linear equation system of debts */ 
	private double[] b;
	
	/**
	 * Creates an empty solver. Call <tt>solve(Collection)</tt> to start calculation.
	 * 
	 */ 
	public HybridSolver() {
		super();
	}
	
	/**
	 * Solves debts of given persons with the default 10000 iterations.
	 * 
	 * @param persons	persons whose debts to calculate
	 */	
	public HybridSolver(Collection<Person> persons) {
		super(persons);
	}

	
	@Override
	protected void calculateSolution() {
		// Check if the system has a unique solution
		createMatrix();
		GaussianLinSysSolver linSysSolver = new GaussianLinSysSolver(A, b);
		if (linSysSolver.getNumberOfFreeVariables() == 0) { 
			logger.log(Level.FINE, "Solution is unique, using only one iteration");
			int tempNumIter = getNumIterations();
			setNumIterations(1);
			super.calculateSolution();
			setNumIterations(tempNumIter);
		} else {
			logger.log(Level.FINE, "Solution is not unique, finding the best with {0} iterations", getNumIterations());
			super.calculateSolution();
		}

	}
	
	/** 
	 * Forms a linear system Ax = b of the debts. 
	 * <p>
	 * When there are d debtors and c creditors, 
	 * the size of solution x is (d*c)*1 and x[c*i + j] is the value of the debt owed 
	 * by debtor i to creditor j.
	 * <p>
	 * Elements of b are balances of the debtors (positive) and creditors (negative)
	 * with the following correspondence:
	 * <p>
	 * b[0]: first debtor <br>
	 * ... <br>
	 * b[debtors.size()-1]: last debtor <br>
	 * b[debtors.size()] = first creditor <br>
	 * ... <br>
	 * b[b.length-1] = last creditor <br>
	 * <p>
	 * The coefficient matrix A is constructed so that for each debtor i, we have equation
	 * where total value of debts to paid by i equals i's balance:<br>
	 * x[c*i] + x[c*i + 1] + ... + x[c*i + c] = b[i] <br>
	 * Coefficients for other elements of x are zero. <br>
	 * For each creditor j, we must have equation where the total value of debts received by j
	 * equals i's balance:<br>
	 * -x[c*i] - x[c*i + 1] - ... -x[c*i + c] = b[i] <br>
	 * Coefficients for other elements of x are zero. <br>
	 * <p>
	 * Thus, the size of the coefficient matrix A is (d+c)*(d*c).
	 * Rows of A indexed between [0, d-1] represent the debtors in the order 
	 * of <code>debtors</code> list. Rows of A indexed between [d, d+c-1] 
	 * represent the creditor in the order of <code>creditors</code> 
	 * list. Values of A are -1, 0, or 1: <br>
	 * 	-1: the person corresponding to the row is the creditor of the debt <br>
	 *	 0: = the person is neither the debtor nor the creditor in the debt <br>
	 * 	 1: the person is the debtor of the debt <br>  
	 */
	private void createMatrix() {
		int d = debtors.size();
		int c = creditors.size();
				
		// Form the RHS vector: first debtors in the list's order, then the creditors
		b = new double[d + c];
		int idx = 0;
		for (Person debtor : debtors) {
			b[idx] = debtor.getBalance();
			++idx;
		}	
		for (Person creditor : creditors) {
			b[idx] = creditor.getBalance();
			++idx;
		}
		
		// Form the coefficient matrix matching the RHS vector
		A = new double[d+c][d*c];
		// Coefficients of equations "sum of debts paid by debtor's = sum debtors balance"    
		for (int i = 0; i < d; ++i) {
			for (int j = i*c; j < (i+1)*c; ++j) {
				A[i][j] = 1;
			}
		}
		// Coefficients of equations "negative sum debts received by creditor = sum creditors credit" 
		for (int i = d; i < c+d; ++i) {
			for (int j = (i-d); j < d*c; j += c) {
				A[i][j] = -1;
			}
		}	
	}

}
